package com.mlh.dp.买卖股票的最佳时机;

/**
 * @author 缪林辉
 * @date 2024/4/27 10:52
 * @DESCRIPTION
 */
// 给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
// 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
public class 买卖股票的最佳时机4 {
    public int method1(int k, int[] prices) {
        //这边会有2*k个状态  偶数为拥有  奇数为未拥有
        k=2*k;
        int[]dp=new int[k];
        //初始化
        for(int i=0;i<k;i+=2){
            dp[i]=-prices[0];
        }
        for(int i=1;i<prices.length;++i){
            for(int j=0;j<k;j++){
                if(j%2==0){//偶数状态定义
                    if(j==0){//0单独定义
                        dp[j]=Math.max(-prices[i],dp[j]);
                    }else{
                        dp[j]=Math.max(dp[j-1]-prices[i],dp[j]);
                    }
                }else {//奇数状态定义
                    dp[j]=Math.max(dp[j-1]+prices[i],dp[j]);
                }
            }
        }
        int res=0;
        //遍历数组，找出最大值
        for(int i=1;i<k;i+=2){
            res=Math.max(dp[i],res);
        }
        return res;
    }
}
